package com.jacklei.ch20;


import java.util.Arrays;

/*
* 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

 

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class MaximumProductSubarray {
            public static void main(String[] args) {
                MaximumProductSubarray m = new MaximumProductSubarray();
                System.out.println(m.maxProduct2(new int[]{
                        1,0,-1,2,3,-5,-2
                        }));

            }
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        int numsMax = Integer.MIN_VALUE;
        for (int num : nums) {
            numsMax = Math.max(num,numsMax);
        }
        int currMax = numsMax;
        int l = 0;
        while (l < len-1) {
            if(nums[l] +1 == nums[l+1]){
                currMax = Math.max(currMax , nums[l] * (nums[l]+1) );
            }
            l++;
        }
        return currMax;
    }
    public int maxProduct1(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        int [][] dp = new int[len] [len+1];
        int currMax = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            dp[i][0] = 0;
            dp[i][1] = nums[i];
            currMax = Math.max(nums[i] , currMax);
        }

        for (int i = 2; i < len+1; i++) {
            dp[0][i] = dp[0][i-1] * dp[i-1][1];
            currMax = Math.max(dp[0][i] , currMax);
        }
        for (int i = 1; i < len; i++) {
            for (int j = 2; j < len+1 - i; j++){
                if (dp[i-1][1] != 0){
                    dp[i][j] = dp[i-1][j+1] / dp[i-1][1];
                }else {
                    dp[i][j] = dp[i][j-1] * dp[i+j-1][1];
                }
                currMax = Math.max(currMax,dp[i][j]);
            }
        }
        return currMax;
    }
    public int maxProduct2(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        int [][] dp = new int[2] [len];
        int currMax = Integer.MIN_VALUE;
        dp[0][0] = nums[0];
        currMax = Math.max(currMax,nums[0]);
        for (int i = 1; i < len; i++) {
            dp[0][i] = dp[0][i-1] *nums[i];
            currMax = Math.max(nums[i] , Math.max( currMax,dp[0][i]));
        }

        for (int i = 1; i < len; i++) {
            dp[1][0] = nums[i];
            for (int j = 1; j < len - i; j++){
                if (nums[i-1] != 0){
                    dp[1][j] = dp[0][j+1] / nums[i-1];
                }else {
                    dp[1][j] = dp[1][j-1] * nums[i+j];
                }
                currMax = Math.max(currMax,dp[1][j]);

            }
            dp[0] = dp[1];
            dp[1] = new int[len];
        }
        return currMax;
    }


}
